package textgen;

import java.util.AbstractList;

import com.sun.corba.se.impl.orbutil.graph.Node;


/** A class that implements a doubly linked list
 * 
 * @author UC San Diego Intermediate Programming MOOC team
 *
 * @param <E> The type of the elements stored in the list
 */
public class MyLinkedList<E> extends AbstractList<E> {
	LLNode<E> head;
	LLNode<E> tail;
	int size;

	/** Create a new empty LinkedList */
	public MyLinkedList() {
		// TODO: Implement this method
		head = new LLNode<E>(null);
		tail = new LLNode<E>(null);
		this.size = 0;
		head.next = tail;
		tail.next = head;
		
	}

	/**
	 * Appends an element to the end of the list
	 * @param element The element to add
	 */
	public boolean add(E element ) 
	{
		if (element == null) {
			throw new NullPointerException();
		}
		
		LLNode<E> node = new LLNode<E>(element);
		if (size==0) {
			this.head.next = node;
			node.next = this.tail;
			node.prev = this.head;
			this.tail.prev = node;
			
		}else {
			node.next = this.tail;
			node.prev = this.tail.prev;
			this.tail.prev.next = node;
			this.tail.prev = node;
			
		}
		
		this.size++;
		
		return true;
	}

	/** Get the element at position index 
	 * @throws IndexOutOfBoundsException if the index is out of bounds. */
	public E get(int index) 
	{
		try {
			LLNode<E> node = this.getNode(index);
			return node.data;
		} catch (IndexOutOfBoundsException e) {
			throw e;
		}
	}

	/**
	 * Add an element to the list at the specified index
	 * @param The index where the element should be added
	 * @param element The element to add
	 */
	public void add(int index, E element ) 
	{
		// TODO: Implement this method
		try {
			if (element ==null) {
				throw new NullPointerException();
			}
			
			
			if (this.size == 0) {
				if (index != 0) {
					throw new IndexOutOfBoundsException();
				}
				
			} else {
				if (index > (this.size -1) || index < 0) {
					throw new IndexOutOfBoundsException();
				}
			}
			
			LLNode<E> nodeAtPreviousIndex = null;
			if (index == 0) {
				nodeAtPreviousIndex = this.head;
			}
			else {
				nodeAtPreviousIndex = this.getNode(index-1);
			}

			LLNode<E> newNode = new LLNode<E>(element);
			newNode.prev = nodeAtPreviousIndex;
			newNode.next = nodeAtPreviousIndex.next;
			nodeAtPreviousIndex.next.prev = newNode;
			nodeAtPreviousIndex.next = newNode;
			
			this.size++;
			
		} catch (IndexOutOfBoundsException e) {
			throw e;
		}
	}


	/** Return the size of the list */
	public int size() 
	{
		return this.size;
	}

	/** Remove a node at the specified index and return its data element.
	 * @param index The index of the element to remove
	 * @return The data element removed
	 * @throws IndexOutOfBoundsException If index is outside the bounds of the list
	 * 
	 */
	public E remove(int index) 
	{
		if (this.size == 0) {
			throw new IndexOutOfBoundsException();
		}else {
			if (index >(this.size-1) || index<0) {
				throw new IndexOutOfBoundsException();
			}
		}
		
		this.size--;
		if (index == 0) {
			LLNode<E> node = this.head.next;
			this.head.next = this.head.next.next;
			this.head.next.prev = this.head;
			return node.data;
		}
		else if (index == (this.size -1)) {
			LLNode<E> node = this.tail.next;
			this.tail.prev = this.tail.prev.prev;
			this.tail.prev.next = this.tail;
			return node.data;
		}
		else {
			LLNode<E> node=this.getNode(index);
			node.prev.next = node.next;
			node.next.prev = node.prev;
			return node.data;
		}
	}

	/**
	 * Set an index position in the list to a new element
	 * @param index The index of the element to change
	 * @param element The new element
	 * @return The element that was replaced
	 * @throws IndexOutOfBoundsException if the index is out of bounds.
	 */
	public E set(int index, E element) 
	{
		// TODO: Implement this method
		
		
		if (size == 0) {
			throw new IndexOutOfBoundsException();
		}
		
		if (index < 0 || index > size-1) {
			throw new IndexOutOfBoundsException();
		}
		
		if (element == null) {
			throw new NullPointerException();
		}
		
		try {
			LLNode<E> node = this.getNode(index);
			E oldValue = node.data;
			node.data = element;			
			return oldValue;
			
		} catch (IndexOutOfBoundsException e) {
			throw e;
		}		
	}
	
	/**
	 * help method that returns the inner node at index.
	 * @param index
	 * @return inner node
	 */
	
	private LLNode<E> getNode(int index) {
		
		int count = index+1;
		if (size==0) {
			throw new IndexOutOfBoundsException();
		}
		if (count>this.size || index < 0) {
			throw new IndexOutOfBoundsException();
		}
		
		LLNode<E> curr = this.head.next;
		while (count-- > 0) {
			if (count==0) {
				return curr;
			}
			else {
				curr = curr.next;
			}
		}
		return null;
	}
}

class LLNode<E> 
{
	LLNode<E> prev;
	LLNode<E> next;
	E data;

	// TODO: Add any other methods you think are useful here
	// E.g. you might want to add another constructor

	public LLNode(E e) 
	{
		this.data = e;
		this.prev = null;
		this.next = null;
	}

}
